package leetcode.code1754;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public String largestMerge(String word1, String word2) {
		StringBuffer ans = new StringBuffer();

		int p1 = 0, p2 = 0;
		int len1 = word1.length(), len2 = word2.length();
		while (p1 < len1 && p2 < len2) {
			char cur1 = word1.charAt(p1);
			char cur2 = word2.charAt(p2);
			if (cur1 < cur2) {
				ans.append(cur2);
				p2++;
			} else if (cur1 > cur2) {
				ans.append(cur1);
				p1++;
			} else {
				int tmp1 = p1;
				int tmp2 = p2;
				while (tmp1 < len1 && tmp2 < len2 && word1.charAt(tmp1) == word2.charAt(tmp2)) {
					tmp1++;
					tmp2++;
				}
				if (tmp1 == len1 || tmp2 == len2) {
					if (tmp1 == len1) {
						ans.append(cur2);
						p2++;
					} else {
						ans.append(cur1);
						p1++;
					}
				} else if (word1.charAt(tmp1) > word2.charAt(tmp2)) {
					ans.append(cur1);
					p1++;
				} else {
					ans.append(cur2);
					p2++;
				}
			}
		}
		while (p1 < len1) {
			ans.append(word1.charAt(p1++));
		}
		while (p2 < len2) {
			ans.append(word2.charAt(p2++));
		}
		return ans.toString();
	}

	@Override
	public void debug4() {
		H.compare("qqqqqqqqqqqqqqqqqeqqqeqeqqeeqqqeeqqeeqqqqqeq",
				this.largestMerge("qqqqqqqqqeqeqqeeqqq", "qqqqqqqqeqqqeeqqeeqqqqqeq"));
		H.compare("cbcabaaaaa", this.largestMerge("cabaa", "bcaaa"));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
